#ifndef NDK_DAY34_AS_LINKEDLIST_HPP
#define NDK_DAY34_AS_LINKEDLIST_HPP

#include <assert.h>

// 单链表节点
template<class E>
struct Node {
    Node<E> *next;
    Node<E> *prev; // 双链表
    E value;

public:
    // 构造函数
    Node(E value, Node<E> *prev, Node<E> *next) {
        this->value = value;
        this->next = next;
        this->prev = prev;
    }
};

// list
template<class E>
class LinkedList {
    // 头节点(头指针)
    Node<E> *head = NULL;
    // 集合的长度
    int len = 0;
    /**
     * 记录尾节点（最后）
     */
    Node<E> *last = NULL;

public:
    /**
     * 添加数据
     * @param e 元素
     */
    void push(E e);

    int size();

    E get(int index);

    // remove insert
    void insert(int index, E e);

    E remove(int index);

    ~LinkedList(); // 析构函数

    Node<E> *node(int i);

    void linkLast(E e);

    void linkBefore(Node<E> *pNode, E e);

    E unlink(Node<E> *pNode);
};

template<class E>
void LinkedList<E>::push(E e) {
    // 添加一个数据
    linkLast(e);
    /*Node<E> *new_node = new Node<E>(e, NULL);

    if (head) {// 0 -> 1 -> 2 -> 3
        // 有头节点
        // head->next = new_node;
        // 找到尾巴节点，有一个特定就是 next 节点为空
        *//*Node<E>* h = head;
        while(h){
            if(h->next == NULL){
                break; // 找到最后一个item
            }
            h = h->next; // 不断地找
        }
        h->next = new_node;*//*
        // 每一次都需要找到最后一个节点  50000
        // 记录 last 节点

        // Node<E> *last = node(len - 1);
        last->next = new_node;// O(1)
    } else { // 没有头节点
        head = new_node;
    }
    last = new_node;*/
    len++;
}

template<class E>
Node<E> *LinkedList<E>::node(int index) { // O(n)
    if(index < (len >> 1)) { // index 在前半部分
        // 从前往后遍历
        Node<E> *cur = head;
        for (int i = 0; i < index; ++i) { // 从i=0，遍历到i==index-1
            cur = cur->next;
        }
        return cur;
    } else {
        // 后半部分：从后往前遍历
        Node<E> *cur = last;
        for (int i = len - 1; i > index; i--) {
            cur = cur->prev;
        }
        return cur;
    }
}

template<class E>
int LinkedList<E>::size() {
    return len;
}

template<class E>
E LinkedList<E>::get(int index) {
    assert(index >= 0 && index < len);
    return node(index)->value;
}

template<class E>
void LinkedList<E>::insert(int index, E e) {// len = 4
    assert(index >= 0 && index <= len); // 断言
    // 考虑边界  0
    if (index == len) {
        linkLast(e); // 添加到末尾
    } else {
        linkBefore(node(index), e);
    }

    /*Node<E> *new_node = new Node<E>(e, NULL);
    if (index == 0) { // 插入第0个位置
        Node<E> *h = head;
        head = new_node;
        new_node->next = h;
    } else {
        // 考虑最后一个位置
        Node<E> *prev = node(index - 1); // 上一个节点
        Node<E> *next = prev->next;// NULL
        prev->next = new_node;
        new_node->next = next;
    }*/

    len++;
}

template<class E>
E LinkedList<E>::remove(int index) {
    // 考虑边界问题  0  ， len , mid
    assert(index >= 0 && index < len);

    return unlink(node(index));

    /*if (index == 0) { // 移除头指针
        Node<E> *h = head;
        head = h->next;
        // 释放
        delete h;
    } else { // 移除中间的节点
        Node<E> *prev = node(index - 1); // 找到它的上一个节点
        // 要删除的节点
        Node<E> *cur = prev->next;
        prev->next = cur->next;
        delete cur;
    }
    len--;
    */
}

template<class E>
LinkedList<E>::~LinkedList() {
    // 析构释放内存 ？
}

template<class E>
void LinkedList<E>::linkLast(E e) {
    Node<E> *l = last; // 缓存的last节点
    Node<E> *new_node = new Node<E>(e, l, NULL); // l是上一个节点，下一个节点是NULL。
    last = new_node;

    if (head) { // head非空
        l->next = new_node;
    } else { // head是空
        head = new_node;
    }
}

// 插入非队尾
template<class E>
void LinkedList<E>::linkBefore(Node<E> *cur, E e) {
    Node<E> *prev = cur->prev;// 可能是NULL(第0个位置)  前一个节点
    // 1.2. 设置newNode的上下Node指针。
    Node<E> *new_node = new Node<E>(e, prev, cur); // cur是要往后移的节点
    // 当前的上一个节点 = 新增的节点
    cur->prev = new_node; // 3.设置cur节点的prev为 新加入的节点
    // 上一个节点的 next -> 新增的节点;  0 特殊处理
    if (prev) { // 4.前节点非空，前节点的next 为新加入点。
        prev->next = new_node;
    } else {// 0 前节点是空。
        head = new_node; // 当前节点，就是头节点。
    }
}

template<class E>
E LinkedList<E>::unlink(Node<E> *cur) { // 删除元素
    // 拿到cur左右两个节点
    Node<E> *prev = cur->prev;
    Node<E> *next = cur->next;
    E value = cur->value;

    // 有两个为空的情况， 严谨 ，思维灵活
    if(prev){
        prev->next = next;
    } else {
        head = next;
    }
    if(next){
        next->prev = prev;
    } else {
        last = prev;
    }

    delete cur;
    len--;
    return value;
}

#endif //NDK_DAY34_AS_TEST_H